//给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数
//目来描述。 
//
// 返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
//输出：[2,11,7,15]
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
//输出：[24,32,8,12]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums1.length <= 10⁵ 
// nums2.length == nums1.length 
// 0 <= nums1[i], nums2[i] <= 10⁹ 
// 
// Related Topics 贪心 数组 排序 👍 193 👎 0

package leetcode.editor.cn;

import javafx.util.Pair;

import java.util.Arrays;
import java.util.PriorityQueue;

// 870. 优势洗牌
// https://leetcode.cn/problems/advantage-shuffle/
class AdvantageShuffle {
    public static void main(String[] args) {
        Solution solution = new AdvantageShuffle().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 参照：labuladong：https://labuladong.github.io/algo/2/19/31/
        // 时间复杂度 O(nlogn)
        /*public int[] advantageCount(int[] nums1, int[] nums2) {
            int n = nums2.length;
            // 需要保存索引，和从小到大拍好nums2，题目要求不改变nums2大小，所以不能对nums2进行降序排序
            PriorityQueue<int[]> queue = new PriorityQueue<>((int[] array1, int[] array2) -> array2[1] - array1[1]);
            for (int i = 0; i < n; i++) {
                queue.offer(new int[]{i, nums2[i]});
            }

            // 对nums1进行排序
            Arrays.sort(nums1);

            int left = 0, right = n - 1;
            int[] res = new int[n];
            while (!queue.isEmpty()) {
                int[] poll = queue.poll();
                int index = poll[0], value = poll[1];
                // 左右指针进行判断
                if (value < nums1[right]) {
                    // 能够匹配直接匹配，因为后边没有比它大的数
                    res[index] = nums1[right];
                    right--;
                } else {
                    // 如果没有能够匹配的，直接使用最小的去做替死鬼
                    res[index] = nums1[left];
                    left++;
                }
            }

            return res;
        }*/

        // 田忌赛马的策略
        // 下等马去pk上等马，过了就删除
        // 如果pk不过，那就去pk别人最好的马，来当作牺牲品
        // https://leetcode.cn/problems/advantage-shuffle/solution/you-shi-xi-pai-by-leetcode-solution-sqsf/
        public int[] advantageCount(int[] nums1, int[] nums2) {
            // nums1,nums2升序排列
            int n = nums1.length;
            Integer[] idx1 = new Integer[n];
            Integer[] idx2 = new Integer[n];

            for (int i = 0; i < n; i++) {
                idx1[i] = i;
                idx2[i] = i;
            }

            Arrays.sort(idx1, (i, j) -> nums1[i] - nums1[j]);
            Arrays.sort(idx2, (i, j) -> nums2[i] - nums2[j]);

            int[] ans = new int[n];
            int l = 0, r = n - 1;
            for (int i = 0; i < n; i++) {
                // 最大的都比他
                if (nums1[idx1[i]] > nums2[idx2[l]]) {
                    ans[idx2[l]] = nums1[idx1[i]];
                    l++;
                } else {
                    // 最小的做替死鬼
                    ans[idx2[r]] = nums1[idx1[i]];
                    r--;
                }
            }

            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
